<?php
/**
 * Created by PhpStorm.
 * User: zd
 * Date: 17-11-7
 * Time: 下午2:31
 */

/**
 * 冒泡排序
 * @param $arr
 * @return mixed
 */
function bubbleSort($arr){
    $len = count($arr);
    //需要冒泡的轮数
    for($i=1;$i<$len;$i++){
        //冒出一个数
        for($k=0;$k<$len-$i;$k++){

            if($arr[$k] > $arr[$k+1]){
                $tmp = $arr[$k+1];
                $arr[$k+1] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }
    return $arr;
}


/**
 * 选择排序
 * @param $arr
 * @return mixed
 */
function selectSort($arr){
    $len = count($arr);

    //循环的轮次
    for($i=0;$i<$len-1;$i++){
        //假设当前是最小的
        $p = $i;

        for($j=$i+1;$j<$len;$j++){
            if($arr[$p] > $arr[$j]){
                $p = $j;
            }
        }

        //查询到最小的元素，放到前面
        if($p != $i){
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }

    return $arr;
}


/**
 * 插入排序
 * @param $arr
 * @return mixed
 */
function insertSort($arr){
    $len = count($arr);

    for($i=1;$i<$len;$i++){
        $tmp = $arr[$i];

        //插入前面是有序的系列
        for($j=$i-1;$j>0;$j--){
            if($tmp < $arr[$j]){
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            }else{
                break;
            }
        }
    }

    return $arr;
}

/**
 * 快速排序
 * @param $arr
 * @return array
 */
function quickSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }

    //选择基准
    $baseNum = $arr[0];

    $leftArr = [];
    $rightArr = [];

    for($i=1;$i<$len;$i++){
        if($baseNum > $arr[$i]){
            //小的放左边
            $leftArr[] = $arr[$i];
        }else{
            //大的放右边
            $rightArr[] = $arr[$i];
        }
    }

    $leftArr = quickSort($leftArr);
    $rightArr = quickSort($rightArr);

    //合并
    return array_merge($leftArr,[$baseNum],$rightArr);
}


$arr=array(1,43,54,62,21,66,32,78,36,76,39);
print_r(bubbleSort($arr));
print_r(selectSort($arr));
print_r(insertSort($arr));
print_r(quickSort($arr));